Programming Logic and Design (3rd ed) by Tony Gaddis

Author:Tony Gaddis [Gaddis, Tony]
Language: eng
Format: epub
ISBN: 0132891301
Published: 2012-01-19T04:37:42+00:00

Sorting and

9 Searching Arrays

CHAPTER

T O P I C S

9.1

The Bubble Sort Algorithm

9.3

The Insertion Sort Algorithm

9.2

The Selection Sort Algorithm

9.4

The Binary Search Algorithm

9.1

The Bubble Sort Algorithm

C O N C E P T: A sorting algorithm rearranges the contents of an array so they appear in a specific order. The bubble sort is a simple sorting algorithm.

Sorting Algorithms

Many programming tasks require that the data in an array be sorted in some order.

Customer lists, for instance, are commonly sorted in alphabetical order, student grades might be sorted from highest to lowest, and product codes could be sorted so all the products of the same color are stored together. To sort the data in an array, the programmer must use an appropriate sorting algorithm. A sorting algorithm is a technique for stepping through an array and rearranging its contents in some order.

The data in an array can be sorted in either ascending or descending order. If an array is sorted in ascending order, it means the values in the array are stored from lowest to highest. If the values are sorted in descending order, they are stored from highest to lowest. This chapter discusses three sorting algorithms that you can use to sort the data in an array: the bubble sort, the selection sort, and the insertion sort. This section examines the bubble sort algorithm.

337

338

Chapter 9

Sorting and Searching Arrays

The Bubble Sort

The bubble sort is an easy way to arrange data in ascending or descending order. It is called the bubble sort algorithm because as it makes passes through and compares the elements of the array, certain values “bubble” toward the end of the array with each pass. For example, if you are using the algorithm to sort an array in ascending order, the larger values move toward the end. If you are using the algorithm to sort an array in descending order, the smaller values move toward the end. In this section you will see how the bubble sort algorithm can be used to sort an array in ascending order.

Suppose we have the array shown in Figure 9-1. Let’s see how the bubble sort can be used in arranging the array’s elements in ascending order.

Figure 9-1 An array

7

2

3

8

9

1

Element 0

Element 1

Element 2

Element 3

Element 4

Element 5

The bubble sort starts by comparing the first two elements in the array. If element 0

is greater than element 1, they are swapped. The array would then appear as shown in Figure 9-2.

Figure 9-2 Elements 0 and 1 are swapped

These elements are

swapped.

2

7

3

8

9

1

Element 0

Element 1

Element 2

Element 3

Element 4

Element 5

This method is repeated with elements 1 and 2. If element 1 is greater than element 2, they are swapped. The array would then appear as shown in Figure 9-3.

Figure 9-3 Elements 1 and 2 are swapped

These elements are

swapped.

2

3

7

8

9

1

Element 0

Element 1

Element 2

Element 3

Element 4

Element 5

Next, elements 2 and 3 are compared. In this array, these elements are already in the proper order (element 2 is less than element 3), so no values are swapped. As the cycle continues, elements 3 and 4 are compared. Once again, it is not necessary to swap the values because they are already in the proper order.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.